Planteamiento¶
Inicialmente se consiguen las coordenadas de todos los circuitos del calendario 2023 de la Formula 1 (Incluyendo el "Autodromo Internazionale Enzo e Dino Ferrari" en Imola, ya que este año se canceló pero inicialmente hacía parte del calendario)
Los datos y el orden de los circuitos se pueden consultar en estos enlaces Wikipedia y Formula1.com
Se obtuvo la latitud y longitud de cada circuito usando la página GeoHack
Mediante la fórmula del semiverseno (Harvesine Formula) se calculan las distancias entre todos ellos y con ellas se construye un grafo representado en un diccionario de diccinarios.
$$d = 2R \, \arcsin \sqrt{\sin^{2} \frac{\varphi_{1} - \varphi_{2}}{2} + \cos\varphi_{1} \cos\varphi_{2} \sin^{2} \frac{\lambda_{1} - \lambda_{2}}{2}}$$
from numpy import sqrt, sin, cos, arcsin, radians
from json import dumps # Para imprimir bien el grafo
circuits = [
('Bahrain International Circuit', 'Sakhir', 'Bahrain', 26.0325, 50.510556),
('Jeddah Corniche Circuit', 'Jeddah', 'Saudi Arabia', 21.631944, 39.104444),
('Albert Park Circuit', 'Melbourne', 'Australia', -37.849722, 144.968333),
('Baku City Circuit', 'Baku', 'Azerbaijan', 40.3725, 49.853333),
('Miami International Autodrome', 'Miami', 'United States', 25.958056, -80.238889),
('Autodromo Internazionale Enzo e Dino Ferrari', 'Imola', 'Italy', 44.341111, 11.713333),
('Circuit de Monaco', 'Montecarlo', 'Monaco', 43.734722, 7.420556),
('Circuit de Barcelona-Catalunya', 'Barcelona', 'Spain', 41.57, 2.261111),
('Circuit Gilles Villeneuve', 'Montreal', 'Canada', 45.500556, -73.5225),
('Red Bull Ring', 'Spielberg', 'Austria', 47.219722, 14.764722),
('Silverstone Circuit', 'Silverstone', 'United Kingdom', 52.078611, -1.016944),
('Hungaroring', 'Budapest', 'Hungary', 47.582222, 19.251111),
('Circuit de Spa-Francorchamps', 'Spa-Francorchamps', 'Belgium', 50.437222, 5.971389),
('Circuit Zandvoort', 'Zandvoort', 'Netherlands', 52.388819, 4.540922),
('Autodromo Nazionale di Monza', 'Monza', 'Italy', 45.620556, 9.289444),
('Marina Bay Street Circuit', 'Marina Bay', 'Singapore', 1.291531, 103.86385),
('Suzuka International Racing Course', 'Suzuka', 'Japan', 34.843056, 136.540556),
('Lusail International Circuit', 'Lusail', 'Qatar', 25.49, 51.454167),
('Circuit of the Americas', 'Austin', 'United States', 30.132778, -97.641111),
('Autódromo Hermanos Rodriguez', 'Mexico City', 'Mexico', 19.406111, -99.0925),
('Autódromo José Carlos Pace', 'Sao Paulo', 'Brazil', -23.701111, -46.697222),
('Las Vegas Strip Circuit', 'Las Vegas', 'United States', 36.119684, -115.172599),
('Yas Marina Circuit', 'Abu Dhabi', 'United Arab Emirates', 24.467222, 54.603056),
]
# Formula para calcular distancias con latitud y longitud (Haversine formula)
def haversineDistance(circuit1, circuit2):
# d = 2R × sin⁻¹(√[sin²((θ₂ - θ₁)/2) + cosθ₁ × cosθ₂ × sin²((φ₂ - φ₁)/2)])
# θ₁, φ₁ – lat1, lon1 -> Radians
# θ₂, φ₂ – lat2, lon2 -> Radians
# R – Radio de la tierra (R = 6371km)
# d = Distancia en Km entre los dos puntos
lat1, lon1 = radians(circuit1[3]), radians(circuit1[4])
lat2, lon2 = radians(circuit2[3]), radians(circuit2[4])
d = 2*6371 * arcsin(sqrt((sin((lat2 - lat1)/2)**2) + (cos(lat1) * cos(lat2) * (sin((lon2 - lon1)/2)**2))))
return round(d, 2)
# Crear y rellenar el grafo con las distancias entre todos los circuitos
def generateGraph(circuits): #O(N^2)
graph = {circuit[1]: {} for circuit in circuits}
for circuit1 in circuits:
city1 = circuit1[1]
# Calcular distancias con cada uno de los otros circuitos
for circuit2 in circuits:
city2 = circuit2[1]
# Poner un infinito como distancia a sí mismo
if city1 == city2:
graph[city1][city2] = float('inf')
continue
d = haversineDistance(circuit1, circuit2)
graph[city1][city2], graph[city2][city1] = d, d
return graph
graph = generateGraph(circuits)
print(dumps(graph, indent=4))
{
"Sakhir": {
"Sakhir": Infinity,
"Jeddah": 1258.42,
"Melbourne": 12112.65,
"Baku": 1595.69,
"Miami": 12185.61,
"Imola": 4018.42,
"Montecarlo": 4332.64,
"Barcelona": 4710.92,
"Montreal": 10258.89,
"Spielberg": 3910.83,
"Silverstone": 5158.07,
"Budapest": 3629.0,
"Spa-Francorchamps": 4640.38,
"Zandvoort": 4805.04,
"Monza": 4242.25,
"Marina Bay": 6327.17,
"Suzuka": 8054.3,
"Lusail": 112.11,
"Austin": 12908.76,
"Mexico City": 13990.04,
"Sao Paulo": 11813.24,
"Las Vegas": 12942.72,
"Abu Dhabi": 446.84
},
"Jeddah": {
"Sakhir": 1258.42,
"Jeddah": Infinity,
"Melbourne": 12817.13,
"Baku": 2317.67,
"Miami": 11605.61,
"Imola": 3559.52,
"Montecarlo": 3810.51,
"Barcelona": 4087.37,
"Montreal": 9929.36,
"Spielberg": 3585.07,
"Silverstone": 4815.75,
"Budapest": 3387.96,
"Spa-Francorchamps": 4307.68,
"Zandvoort": 4515.09,
"Monza": 3797.32,
"Marina Bay": 7353.78,
"Suzuka": 9293.26,
"Lusail": 1329.12,
"Austin": 12632.6,
"Mexico City": 13574.55,
"Sao Paulo": 10555.29,
"Las Vegas": 13046.96,
"Abu Dhabi": 1615.84
},
"Melbourne": {
"Sakhir": 12112.65,
"Jeddah": 12817.13,
"Melbourne": Infinity,
"Baku": 12989.09,
"Miami": 15594.44,
"Imola": 16086.6,
"Montecarlo": 16422.24,
"Barcelona": 16823.36,
"Montreal": 16741.08,
"Spielberg": 15878.76,
"Silverstone": 16947.24,
"Budapest": 15546.29,
"Spa-Francorchamps": 16511.75,
"Zandvoort": 16572.56,
"Monza": 16287.46,
"Marina Bay": 6057.73,
"Suzuka": 8129.71,
"Lusail": 12000.57,
"Austin": 14286.03,
"Mexico City": 13563.72,
"Sao Paulo": 13063.22,
"Las Vegas": 13131.4,
"Abu Dhabi": 11674.78
},
"Baku": {
"Sakhir": 1595.69,
"Jeddah": 2317.67,
"Melbourne": 12989.09,
"Baku": Infinity,
"Miami": 11015.92,
"Imola": 3136.08,
"Montecarlo": 3484.88,
"Barcelona": 3946.5,
"Montreal": 8930.46,
"Spielberg": 2890.54,
"Silverstone": 4030.59,
"Budapest": 2557.24,
"Spa-Francorchamps": 3545.36,
"Zandvoort": 3652.58,
"Monza": 3313.73,
"Marina Bay": 6946.61,
"Suzuka": 7342.51,
"Lusail": 1661.5,
"Austin": 11489.36,
"Mexico City": 12631.8,
"Sao Paulo": 12217.45,
"Las Vegas": 11372.96,
"Abu Dhabi": 1823.13
},
"Miami": {
"Sakhir": 12185.61,
"Jeddah": 11605.61,
"Melbourne": 15594.44,
"Baku": 11015.92,
"Miami": Infinity,
"Imola": 8172.77,
"Montecarlo": 7870.82,
"Barcelona": 7536.28,
"Montreal": 2253.95,
"Spielberg": 8278.96,
"Silverstone": 7043.57,
"Budapest": 8573.81,
"Spa-Francorchamps": 7556.52,
"Zandvoort": 7408.91,
"Monza": 7945.63,
"Marina Bay": 16953.17,
"Suzuka": 12224.23,
"Lusail": 12295.51,
"Austin": 1767.7,
"Mexico City": 2064.2,
"Sao Paulo": 6596.07,
"Las Vegas": 3492.79,
"Abu Dhabi": 12600.08
},
"Imola": {
"Sakhir": 4018.42,
"Jeddah": 3559.52,
"Melbourne": 16086.6,
"Baku": 3136.08,
"Miami": 8172.77,
"Imola": Infinity,
"Montecarlo": 349.66,
"Barcelona": 828.03,
"Montreal": 6372.16,
"Spielberg": 397.99,
"Silverstone": 1273.43,
"Budapest": 684.63,
"Spa-Francorchamps": 803.4,
"Zandvoort": 1038.81,
"Monza": 237.86,
"Marina Bay": 10078.12,
"Suzuka": 9598.9,
"Lusail": 4129.41,
"Austin": 9074.85,
"Mexico City": 10054.55,
"Sao Paulo": 9611.69,
"Las Vegas": 9591.62,
"Abu Dhabi": 4444.1
},
"Montecarlo": {
"Sakhir": 4332.64,
"Jeddah": 3810.51,
"Melbourne": 16422.24,
"Baku": 3484.88,
"Miami": 7870.82,
"Imola": 349.66,
"Montecarlo": Infinity,
"Barcelona": 485.64,
"Montreal": 6121.68,
"Spielberg": 690.95,
"Silverstone": 1119.23,
"Budapest": 1012.7,
"Spa-Francorchamps": 753.28,
"Zandvoort": 985.59,
"Monza": 256.51,
"Marina Bay": 10425.03,
"Suzuka": 9874.92,
"Lusail": 4444.16,
"Austin": 8824.29,
"Mexico City": 9778.17,
"Sao Paulo": 9305.99,
"Las Vegas": 9413.47,
"Abu Dhabi": 4763.02
},
"Barcelona": {
"Sakhir": 4710.92,
"Jeddah": 4087.37,
"Melbourne": 16823.36,
"Baku": 3946.5,
"Miami": 7536.28,
"Imola": 828.03,
"Montecarlo": 485.64,
"Barcelona": Infinity,
"Montreal": 5891.46,
"Spielberg": 1173.28,
"Silverstone": 1194.5,
"Budapest": 1498.27,
"Spa-Francorchamps": 1026.45,
"Zandvoort": 1215.2,
"Monza": 722.86,
"Marina Bay": 10873.33,
"Suzuka": 10323.58,
"Lusail": 4822.98,
"Austin": 8582.42,
"Mexico City": 9487.4,
"Sao Paulo": 8834.48,
"Las Vegas": 9287.99,
"Abu Dhabi": 5148.62
},
"Montreal": {
"Sakhir": 10258.89,
"Jeddah": 9929.36,
"Melbourne": 16741.08,
"Baku": 8930.46,
"Miami": 2253.95,
"Imola": 6372.16,
"Montecarlo": 6121.68,
"Barcelona": 5891.46,
"Montreal": Infinity,
"Spielberg": 6390.43,
"Silverstone": 5137.16,
"Budapest": 6644.58,
"Spa-Francorchamps": 5654.94,
"Zandvoort": 5470.17,
"Monza": 6134.8,
"Marina Bay": 14805.68,
"Suzuka": 10583.98,
"Lusail": 10362.75,
"Austin": 2703.24,
"Mexico City": 3731.52,
"Sao Paulo": 8159.53,
"Las Vegas": 3612.48,
"Abu Dhabi": 10635.83
},
"Spielberg": {
"Sakhir": 3910.83,
"Jeddah": 3585.07,
"Melbourne": 15878.76,
"Baku": 2890.54,
"Miami": 8278.96,
"Imola": 397.99,
"Montecarlo": 690.95,
"Barcelona": 1173.28,
"Montreal": 6390.43,
"Spielberg": Infinity,
"Silverstone": 1254.64,
"Budapest": 340.01,
"Spa-Francorchamps": 735.75,
"Zandvoort": 930.58,
"Monza": 455.69,
"Marina Bay": 9834.11,
"Suzuka": 9203.96,
"Lusail": 4019.63,
"Austin": 9083.34,
"Mexico City": 10104.57,
"Sao Paulo": 9994.29,
"Las Vegas": 9494.42,
"Abu Dhabi": 4321.12
},
"Silverstone": {
"Sakhir": 5158.07,
"Jeddah": 4815.75,
"Melbourne": 16947.24,
"Baku": 4030.59,
"Miami": 7043.57,
"Imola": 1273.43,
"Montecarlo": 1119.23,
"Barcelona": 1194.5,
"Montreal": 5137.16,
"Spielberg": 1254.64,
"Silverstone": Infinity,
"Budapest": 1531.29,
"Spa-Francorchamps": 519.16,
"Zandvoort": 379.97,
"Monza": 1039.49,
"Marina Bay": 10902.48,
"Suzuka": 9507.07,
"Lusail": 5265.9,
"Austin": 7833.24,
"Mexico City": 8850.1,
"Sao Paulo": 9522.4,
"Las Vegas": 8319.6,
"Abu Dhabi": 5561.33
},
"Budapest": {
"Sakhir": 3629.0,
"Jeddah": 3387.96,
"Melbourne": 15546.29,
"Baku": 2557.24,
"Miami": 8573.81,
"Imola": 684.63,
"Montecarlo": 1012.7,
"Barcelona": 1498.27,
"Montreal": 6644.58,
"Spielberg": 340.01,
"Silverstone": 1531.29,
"Budapest": Infinity,
"Spa-Francorchamps": 1017.62,
"Zandvoort": 1176.78,
"Monza": 791.06,
"Marina Bay": 9497.62,
"Suzuka": 8932.35,
"Lusail": 3736.24,
"Austin": 9326.25,
"Mexico City": 10369.32,
"Sao Paulo": 10294.49,
"Las Vegas": 9664.72,
"Abu Dhabi": 4030.08
},
"Spa-Francorchamps": {
"Sakhir": 4640.38,
"Jeddah": 4307.68,
"Melbourne": 16511.75,
"Baku": 3545.36,
"Miami": 7556.52,
"Imola": 803.4,
"Montecarlo": 753.28,
"Barcelona": 1026.45,
"Montreal": 5654.94,
"Spielberg": 735.75,
"Silverstone": 519.16,
"Budapest": 1017.62,
"Spa-Francorchamps": Infinity,
"Zandvoort": 238.6,
"Monza": 589.54,
"Marina Bay": 10454.26,
"Suzuka": 9366.27,
"Lusail": 4748.49,
"Austin": 8349.21,
"Mexico City": 9369.25,
"Sao Paulo": 9728.52,
"Las Vegas": 8800.37,
"Abu Dhabi": 5045.71
},
"Zandvoort": {
"Sakhir": 4805.04,
"Jeddah": 4515.09,
"Melbourne": 16572.56,
"Baku": 3652.58,
"Miami": 7408.91,
"Imola": 1038.81,
"Montecarlo": 985.59,
"Barcelona": 1215.2,
"Montreal": 5470.17,
"Spielberg": 930.58,
"Silverstone": 379.97,
"Budapest": 1176.78,
"Spa-Francorchamps": 238.6,
"Zandvoort": Infinity,
"Monza": 828.04,
"Marina Bay": 10524.08,
"Suzuka": 9257.63,
"Lusail": 4911.88,
"Austin": 8157.69,
"Mexico City": 9192.85,
"Sao Paulo": 9807.17,
"Las Vegas": 8577.34,
"Abu Dhabi": 5202.6
},
"Monza": {
"Sakhir": 4242.25,
"Jeddah": 3797.32,
"Melbourne": 16287.46,
"Baku": 3313.73,
"Miami": 7945.63,
"Imola": 237.86,
"Montecarlo": 256.51,
"Barcelona": 722.86,
"Montreal": 6134.8,
"Spielberg": 455.69,
"Silverstone": 1039.49,
"Budapest": 791.06,
"Spa-Francorchamps": 589.54,
"Zandvoort": 828.04,
"Monza": Infinity,
"Marina Bay": 10260.26,
"Suzuka": 9619.4,
"Lusail": 4352.89,
"Austin": 8837.36,
"Mexico City": 9819.9,
"Sao Paulo": 9555.17,
"Las Vegas": 9359.03,
"Abu Dhabi": 4664.98
},
"Marina Bay": {
"Sakhir": 6327.17,
"Jeddah": 7353.78,
"Melbourne": 6057.73,
"Baku": 6946.61,
"Miami": 16953.17,
"Imola": 10078.12,
"Montecarlo": 10425.03,
"Barcelona": 10873.33,
"Montreal": 14805.68,
"Spielberg": 9834.11,
"Silverstone": 10902.48,
"Budapest": 9497.62,
"Spa-Francorchamps": 10454.26,
"Zandvoort": 10524.08,
"Monza": 10260.26,
"Marina Bay": Infinity,
"Suzuka": 5035.94,
"Lusail": 6219.23,
"Austin": 15843.03,
"Mexico City": 16612.99,
"Sao Paulo": 15982.53,
"Las Vegas": 14219.52,
"Abu Dhabi": 5882.31
},
"Suzuka": {
"Sakhir": 8054.3,
"Jeddah": 9293.26,
"Melbourne": 8129.71,
"Baku": 7342.51,
"Miami": 12224.23,
"Imola": 9598.9,
"Montecarlo": 9874.92,
"Barcelona": 10323.58,
"Montreal": 10583.98,
"Spielberg": 9203.96,
"Silverstone": 9507.07,
"Budapest": 8932.35,
"Spa-Francorchamps": 9366.27,
"Zandvoort": 9257.63,
"Monza": 9619.4,
"Marina Bay": 5035.94,
"Suzuka": Infinity,
"Lusail": 8003.94,
"Austin": 10829.02,
"Mexico City": 11598.54,
"Sao Paulo": 18737.21,
"Las Vegas": 9184.92,
"Abu Dhabi": 7787.84
},
"Lusail": {
"Sakhir": 112.11,
"Jeddah": 1329.12,
"Melbourne": 12000.57,
"Baku": 1661.5,
"Miami": 12295.51,
"Imola": 4129.41,
"Montecarlo": 4444.16,
"Barcelona": 4822.98,
"Montreal": 10362.75,
"Spielberg": 4019.63,
"Silverstone": 5265.9,
"Budapest": 3736.24,
"Spa-Francorchamps": 4748.49,
"Zandvoort": 4911.88,
"Monza": 4352.89,
"Marina Bay": 6219.23,
"Suzuka": 8003.94,
"Lusail": Infinity,
"Austin": 13008.45,
"Mexico City": 14094.18,
"Sao Paulo": 11883.26,
"Las Vegas": 13022.06,
"Abu Dhabi": 337.14
},
"Austin": {
"Sakhir": 12908.76,
"Jeddah": 12632.6,
"Melbourne": 14286.03,
"Baku": 11489.36,
"Miami": 1767.7,
"Imola": 9074.85,
"Montecarlo": 8824.29,
"Barcelona": 8582.42,
"Montreal": 2703.24,
"Spielberg": 9083.34,
"Silverstone": 7833.24,
"Budapest": 9326.25,
"Spa-Francorchamps": 8349.21,
"Zandvoort": 8157.69,
"Monza": 8837.36,
"Marina Bay": 15843.03,
"Suzuka": 10829.02,
"Lusail": 13008.45,
"Austin": Infinity,
"Mexico City": 1201.68,
"Sao Paulo": 8085.15,
"Las Vegas": 1759.74,
"Abu Dhabi": 13260.62
},
"Mexico City": {
"Sakhir": 13990.04,
"Jeddah": 13574.55,
"Melbourne": 13563.72,
"Baku": 12631.8,
"Miami": 2064.2,
"Imola": 10054.55,
"Montecarlo": 9778.17,
"Barcelona": 9487.4,
"Montreal": 3731.52,
"Spielberg": 10104.57,
"Silverstone": 8850.1,
"Budapest": 10369.32,
"Spa-Francorchamps": 9369.25,
"Zandvoort": 9192.85,
"Monza": 9819.9,
"Marina Bay": 16612.99,
"Suzuka": 11598.54,
"Lusail": 14094.18,
"Austin": 1201.68,
"Mexico City": Infinity,
"Sao Paulo": 7431.29,
"Las Vegas": 2433.3,
"Abu Dhabi": 14365.97
},
"Sao Paulo": {
"Sakhir": 11813.24,
"Jeddah": 10555.29,
"Melbourne": 13063.22,
"Baku": 12217.45,
"Miami": 6596.07,
"Imola": 9611.69,
"Montecarlo": 9305.99,
"Barcelona": 8834.48,
"Montreal": 8159.53,
"Spielberg": 9994.29,
"Silverstone": 9522.4,
"Budapest": 10294.49,
"Spa-Francorchamps": 9728.52,
"Zandvoort": 9807.17,
"Monza": 9555.17,
"Marina Bay": 15982.53,
"Suzuka": 18737.21,
"Lusail": 11883.26,
"Austin": 8085.15,
"Mexico City": 7431.29,
"Sao Paulo": Infinity,
"Las Vegas": 9788.14,
"Abu Dhabi": 12148.74
},
"Las Vegas": {
"Sakhir": 12942.72,
"Jeddah": 13046.96,
"Melbourne": 13131.4,
"Baku": 11372.96,
"Miami": 3492.79,
"Imola": 9591.62,
"Montecarlo": 9413.47,
"Barcelona": 9287.99,
"Montreal": 3612.48,
"Spielberg": 9494.42,
"Silverstone": 8319.6,
"Budapest": 9664.72,
"Spa-Francorchamps": 8800.37,
"Zandvoort": 8577.34,
"Monza": 9359.03,
"Marina Bay": 14219.52,
"Suzuka": 9184.92,
"Lusail": 13022.06,
"Austin": 1759.74,
"Mexico City": 2433.3,
"Sao Paulo": 9788.14,
"Las Vegas": Infinity,
"Abu Dhabi": 13193.06
},
"Abu Dhabi": {
"Sakhir": 446.84,
"Jeddah": 1615.84,
"Melbourne": 11674.78,
"Baku": 1823.13,
"Miami": 12600.08,
"Imola": 4444.1,
"Montecarlo": 4763.02,
"Barcelona": 5148.62,
"Montreal": 10635.83,
"Spielberg": 4321.12,
"Silverstone": 5561.33,
"Budapest": 4030.08,
"Spa-Francorchamps": 5045.71,
"Zandvoort": 5202.6,
"Monza": 4664.98,
"Marina Bay": 5882.31,
"Suzuka": 7787.84,
"Lusail": 337.14,
"Austin": 13260.62,
"Mexico City": 14365.97,
"Sao Paulo": 12148.74,
"Las Vegas": 13193.06,
"Abu Dhabi": Infinity
}
}
# Distancia recorrida actual en kilometros
currentTotalDistance = 0
for i in range(1, len(circuits)):
currentTotalDistance += haversineDistance(circuits[i-1], circuits[i])
print(f'Total recorrido: {round(currentTotalDistance, 2)} Km')
Total recorrido: 132163.47 Km
En primer lugar se realiza una aproximación greedy al problema. Por lo que se convierte el grafo en una representación matricial y la solución inicial consiste en elegir por cada fila la distancia más cercana a recorrer en el próximo paso.
from prettytable import PrettyTable # Para imprimir bien la matriz
# Se usará una matriz en vez del diccionario de diccionarios
matrix = [list(j.values()) for (_, j) in graph.items()]
p = PrettyTable()
for row in matrix: p.add_row(row)
print(p.get_string(header=False, border=False))
inf 1258.42 12112.65 1595.69 12185.61 4018.42 4332.64 4710.92 10258.89 3910.83 5158.07 3629.0 4640.38 4805.04 4242.25 6327.17 8054.3 112.11 12908.76 13990.04 11813.24 12942.72 446.84 1258.42 inf 12817.13 2317.67 11605.61 3559.52 3810.51 4087.37 9929.36 3585.07 4815.75 3387.96 4307.68 4515.09 3797.32 7353.78 9293.26 1329.12 12632.6 13574.55 10555.29 13046.96 1615.84 12112.65 12817.13 inf 12989.09 15594.44 16086.6 16422.24 16823.36 16741.08 15878.76 16947.24 15546.29 16511.75 16572.56 16287.46 6057.73 8129.71 12000.57 14286.03 13563.72 13063.22 13131.4 11674.78 1595.69 2317.67 12989.09 inf 11015.92 3136.08 3484.88 3946.5 8930.46 2890.54 4030.59 2557.24 3545.36 3652.58 3313.73 6946.61 7342.51 1661.5 11489.36 12631.8 12217.45 11372.96 1823.13 12185.61 11605.61 15594.44 11015.92 inf 8172.77 7870.82 7536.28 2253.95 8278.96 7043.57 8573.81 7556.52 7408.91 7945.63 16953.17 12224.23 12295.51 1767.7 2064.2 6596.07 3492.79 12600.08 4018.42 3559.52 16086.6 3136.08 8172.77 inf 349.66 828.03 6372.16 397.99 1273.43 684.63 803.4 1038.81 237.86 10078.12 9598.9 4129.41 9074.85 10054.55 9611.69 9591.62 4444.1 4332.64 3810.51 16422.24 3484.88 7870.82 349.66 inf 485.64 6121.68 690.95 1119.23 1012.7 753.28 985.59 256.51 10425.03 9874.92 4444.16 8824.29 9778.17 9305.99 9413.47 4763.02 4710.92 4087.37 16823.36 3946.5 7536.28 828.03 485.64 inf 5891.46 1173.28 1194.5 1498.27 1026.45 1215.2 722.86 10873.33 10323.58 4822.98 8582.42 9487.4 8834.48 9287.99 5148.62 10258.89 9929.36 16741.08 8930.46 2253.95 6372.16 6121.68 5891.46 inf 6390.43 5137.16 6644.58 5654.94 5470.17 6134.8 14805.68 10583.98 10362.75 2703.24 3731.52 8159.53 3612.48 10635.83 3910.83 3585.07 15878.76 2890.54 8278.96 397.99 690.95 1173.28 6390.43 inf 1254.64 340.01 735.75 930.58 455.69 9834.11 9203.96 4019.63 9083.34 10104.57 9994.29 9494.42 4321.12 5158.07 4815.75 16947.24 4030.59 7043.57 1273.43 1119.23 1194.5 5137.16 1254.64 inf 1531.29 519.16 379.97 1039.49 10902.48 9507.07 5265.9 7833.24 8850.1 9522.4 8319.6 5561.33 3629.0 3387.96 15546.29 2557.24 8573.81 684.63 1012.7 1498.27 6644.58 340.01 1531.29 inf 1017.62 1176.78 791.06 9497.62 8932.35 3736.24 9326.25 10369.32 10294.49 9664.72 4030.08 4640.38 4307.68 16511.75 3545.36 7556.52 803.4 753.28 1026.45 5654.94 735.75 519.16 1017.62 inf 238.6 589.54 10454.26 9366.27 4748.49 8349.21 9369.25 9728.52 8800.37 5045.71 4805.04 4515.09 16572.56 3652.58 7408.91 1038.81 985.59 1215.2 5470.17 930.58 379.97 1176.78 238.6 inf 828.04 10524.08 9257.63 4911.88 8157.69 9192.85 9807.17 8577.34 5202.6 4242.25 3797.32 16287.46 3313.73 7945.63 237.86 256.51 722.86 6134.8 455.69 1039.49 791.06 589.54 828.04 inf 10260.26 9619.4 4352.89 8837.36 9819.9 9555.17 9359.03 4664.98 6327.17 7353.78 6057.73 6946.61 16953.17 10078.12 10425.03 10873.33 14805.68 9834.11 10902.48 9497.62 10454.26 10524.08 10260.26 inf 5035.94 6219.23 15843.03 16612.99 15982.53 14219.52 5882.31 8054.3 9293.26 8129.71 7342.51 12224.23 9598.9 9874.92 10323.58 10583.98 9203.96 9507.07 8932.35 9366.27 9257.63 9619.4 5035.94 inf 8003.94 10829.02 11598.54 18737.21 9184.92 7787.84 112.11 1329.12 12000.57 1661.5 12295.51 4129.41 4444.16 4822.98 10362.75 4019.63 5265.9 3736.24 4748.49 4911.88 4352.89 6219.23 8003.94 inf 13008.45 14094.18 11883.26 13022.06 337.14 12908.76 12632.6 14286.03 11489.36 1767.7 9074.85 8824.29 8582.42 2703.24 9083.34 7833.24 9326.25 8349.21 8157.69 8837.36 15843.03 10829.02 13008.45 inf 1201.68 8085.15 1759.74 13260.62 13990.04 13574.55 13563.72 12631.8 2064.2 10054.55 9778.17 9487.4 3731.52 10104.57 8850.1 10369.32 9369.25 9192.85 9819.9 16612.99 11598.54 14094.18 1201.68 inf 7431.29 2433.3 14365.97 11813.24 10555.29 13063.22 12217.45 6596.07 9611.69 9305.99 8834.48 8159.53 9994.29 9522.4 10294.49 9728.52 9807.17 9555.17 15982.53 18737.21 11883.26 8085.15 7431.29 inf 9788.14 12148.74 12942.72 13046.96 13131.4 11372.96 3492.79 9591.62 9413.47 9287.99 3612.48 9494.42 8319.6 9664.72 8800.37 8577.34 9359.03 14219.52 9184.92 13022.06 1759.74 2433.3 9788.14 inf 13193.06 446.84 1615.84 11674.78 1823.13 12600.08 4444.1 4763.02 5148.62 10635.83 4321.12 5561.33 4030.08 5045.71 5202.6 4664.98 5882.31 7787.84 337.14 13260.62 14365.97 12148.74 13193.06 inf
def greedyRoute(graph, firstCity): # O(N^2)
# Conseguir la matriz a partir del diccionario de diccionarios
matrix = [list(j.values()) for (_, j) in graph.items()] #O(N)
totalDistance = 0
route = []
# Tener en cuenta la primera ciudad
currentCity = firstCity
route.append(currentCity)
while len(route) < len(graph):
# Se busca la mínima distancia a la próxima ciudad disponible
minDistance = min(matrix[currentCity])
nextCity = matrix[currentCity].index(minDistance)
# Sumar la distancia a recorrer al total recorrido
totalDistance += minDistance
# Como ya se visitó la ciudad actual, se hace "inaccesible"
for row in range(len(matrix)):
matrix[row][currentCity] = float('inf')
# Se visita la siguiente ciudad y se repite el mismo proceso
route.append(nextCity)
currentCity = nextCity
return totalDistance, route
# Probar el algoritmo usando como punto de partida cada ciudad y buscar el menor
bestDistance, bestRoute = float('inf'), []
for i in range(len(graph)): # O(N^3)
distance, route = greedyRoute(graph, i)
if distance < bestDistance:
bestDistance, bestRoute = distance, route
# Imprimir los resultados
print(f'Total recorrido: {round(bestDistance, 2)} Km')
print(f'Mejora con respecto al actual: {round(((currentTotalDistance-bestDistance)/currentTotalDistance)*100, 2)}%')
print('\nRuta:')
for i, city in enumerate(bestRoute):
print(f'{i+1}. {circuits[city][1]}, {circuits[city][2]}')
Total recorrido: 51280.4 Km Mejora con respecto al actual: 61.2% Ruta: 1. Sao Paulo, Brazil 2. Miami, United States 3. Austin, United States 4. Mexico City, Mexico 5. Las Vegas, United States 6. Montreal, Canada 7. Silverstone, United Kingdom 8. Zandvoort, Netherlands 9. Spa-Francorchamps, Belgium 10. Monza, Italy 11. Imola, Italy 12. Montecarlo, Monaco 13. Barcelona, Spain 14. Spielberg, Austria 15. Budapest, Hungary 16. Baku, Azerbaijan 17. Sakhir, Bahrain 18. Lusail, Qatar 19. Abu Dhabi, United Arab Emirates 20. Jeddah, Saudi Arabia 21. Marina Bay, Singapore 22. Suzuka, Japan 23. Melbourne, Australia
Se observa que esta aproximación disminuye la distancia total recorrida comparado con la actual en un 61.2%, pero esta aproximación no es totalmente óptima, por lo que en los lugares aledaños a los "problemáticos" se opta por calcular la organización de estos nodos usando búsqueda exhaustiva
En primer lugar, se identifica un potencial de mejoramiento en el recorrido de los nodos del continente americano (Nodos 1-6). Actualmente se recorren de esta manera:
Como en este cruce entran en juego 6 nodos, es posible permitirse usar búsqueda exhaustiva para buscar la mejor solución, ya que hay solo 720 combinaciones posibles.
from itertools import permutations
circuits1 = [
('Autódromo José Carlos Pace', 'Sao Paulo', 'Brazil', -23.701111, -46.697222),
('Miami International Autodrome', 'Miami', 'United States', 25.958056, -80.238889),
('Circuit of the Americas', 'Austin', 'United States', 30.132778, -97.641111),
('Autódromo Hermanos Rodriguez', 'Mexico City', 'Mexico', 19.406111, -99.0925),
('Las Vegas Strip Circuit', 'Las Vegas', 'United States', 36.119684, -115.172599),
('Circuit Gilles Villeneuve', 'Montreal', 'Canada', 45.500556, -73.5225),
]
# Distancia recorrida actual de esos nodos
currentDistance = 0
for i in range(1, len(circuits1)):
currentDistance += haversineDistance(circuits1[i-1], circuits1[i])
# Generar todos los posibles recorridos
array = [i for i in range(len(circuits1))]
perms = permutations(array)
# Solo se necesitan los recorridos que empiezan en Sao Paulo y terminan en Montreal
perms = list(filter(lambda i: i[0] == 0 and i[-1] == 5, perms))
print(f'Complejidad: {len(perms)} posibles soluciones\n')
# Hacer la búsqueda exhaustiva buscando la ruta más corta
bestDistance, bestRoute = float('inf'), []
for perm in perms:
distance = 0
for i in range(1, len(perm)):
distance += haversineDistance(circuits1[perm[i-1]], circuits1[perm[i]])
if distance < bestDistance:
bestDistance, bestRoute = distance, perm
# Imprimir los resultados
print(f'Total recorrido actual: {round(currentDistance, 2)} Km')
print(f'Total recorrido óptimo: {round(bestDistance, 2)} Km')
print(f'Mejora con respecto al actual: {round(((currentDistance-bestDistance)/currentDistance)*100, 2)}%')
print('\nRuta:')
for i, city in enumerate(bestRoute):
print(f'{i+1}. {circuits1[city][1]}, {circuits1[city][2]}')
Complejidad: 24 posibles soluciones Total recorrido actual: 15611.23 Km Total recorrido óptimo: 15234.17 Km Mejora con respecto al actual: 2.42% Ruta: 1. Sao Paulo, Brazil 2. Miami, United States 3. Mexico City, Mexico 4. Austin, United States 5. Las Vegas, United States 6. Montreal, Canada
Este es el punto más crítico ya que al recorrer los nodos 9-14 se crea un cruce, que indica que este sub-recorrido no es óptimo.
Como en este cruce entran en juego 6 nodos, se puede permitir usar búsqueda exhaustiva para buscar la mejor solución, ya que hay solo 720 combinaciones posibles.
from itertools import permutations
circuits1 = [
('Circuit de Spa-Francorchamps', 'Spa-Francorchamps', 'Belgium', 50.437222, 5.971389),
('Autodromo Nazionale di Monza', 'Monza', 'Italy', 45.620556, 9.289444),
('Autodromo Internazionale Enzo e Dino Ferrari', 'Imola', 'Italy', 44.341111, 11.713333),
('Circuit de Monaco', 'Montecarlo', 'Monaco', 43.734722, 7.420556),
('Circuit de Barcelona-Catalunya', 'Barcelona', 'Spain', 41.57, 2.261111),
('Red Bull Ring', 'Spielberg', 'Austria', 47.219722, 14.764722),
]
# Distancia recorrida actual de esos nodos
currentDistance = 0
for i in range(1, len(circuits1)):
currentDistance += haversineDistance(circuits1[i-1], circuits1[i])
# Generar todos los posibles recorridos
array = [i for i in range(len(circuits1))]
perms = permutations(array)
# Solo se necesitan los recorridos que empiezan en Spa-Francorchamps y terminan en Spielberg
perms = list(filter(lambda i: i[0] == 0 and i[-1] == 5, perms))
print(f'Complejidad: {len(perms)} posibles soluciones\n')
# Hacer la búsqueda exhaustiva buscando la ruta más corta
bestDistance, bestRoute = float('inf'), []
for perm in perms:
distance = 0
for i in range(1, len(perm)):
distance += haversineDistance(circuits1[perm[i-1]], circuits1[perm[i]])
if distance < bestDistance:
bestDistance, bestRoute = distance, perm
# Imprimir los resultados
print(f'Total recorrido actual: {round(currentDistance, 2)} Km')
print(f'Total recorrido óptimo: {round(bestDistance, 2)} Km')
print(f'Mejora con respecto al actual: {round(((currentDistance-bestDistance)/currentDistance)*100, 2)}%')
print('\nRuta:')
for i, city in enumerate(bestRoute):
print(f'{i+9}. {circuits1[city][1]}, {circuits1[city][2]}')
Complejidad: 24 posibles soluciones Total recorrido actual: 2835.98 Km Total recorrido óptimo: 2404.45 Km Mejora con respecto al actual: 15.22% Ruta: 9. Spa-Francorchamps, Belgium 10. Barcelona, Spain 11. Montecarlo, Monaco 12. Monza, Italy 13. Imola, Italy 14. Spielberg, Austria
Similar al caso anterior, aunque sin un cruce, notamos potencial de mejora en ese subconjunto del recorrido
Como en este cruce entran en juego 6 nodos, se puede permitir usar búsqueda exhaustiva para buscar la mejor solución, ya que hay solo 720 combinaciones posibles.
from itertools import permutations
circuits1 = [
('Baku City Circuit', 'Baku', 'Azerbaijan', 40.3725, 49.853333),
('Bahrain International Circuit', 'Sakhir', 'Bahrain', 26.0325, 50.510556),
('Lusail International Circuit', 'Lusail', 'Qatar', 25.49, 51.454167),
('Yas Marina Circuit', 'Abu Dhabi', 'United Arab Emirates', 24.467222, 54.603056),
('Jeddah Corniche Circuit', 'Jeddah', 'Saudi Arabia', 21.631944, 39.104444),
('Marina Bay Street Circuit', 'Marina Bay', 'Singapore', 1.291531, 103.86385),
]
# Distancia recorrida actual de esos nodos
currentDistance = 0
for i in range(1, len(circuits1)):
currentDistance += haversineDistance(circuits1[i-1], circuits1[i])
# Generar todos los posibles recorridos
array = [i for i in range(len(circuits1))]
perms = permutations(array)
# Solo se necesitan los recorridos que empiezan en Baku y terminan en Marina Bay
perms = list(filter(lambda i: i[0] == 0 and i[-1] == 5, perms))
print(f'Complejidad: {len(perms)} posibles soluciones\n')
# Hacer la búsqueda exhaustiva buscando la ruta más corta
bestDistance, bestRoute = float('inf'), []
for perm in perms:
distance = 0
for i in range(1, len(perm)):
distance += haversineDistance(circuits1[perm[i-1]], circuits1[perm[i]])
if distance < bestDistance:
bestDistance, bestRoute = distance, perm
# Imprimir los resultados
print(f'Total recorrido actual: {round(currentDistance, 2)}Km')
print(f'Total recorrido óptimo: {round(bestDistance, 2)}Km')
print(f'Mejora con respecto al actual: {round(((currentDistance-bestDistance)/currentDistance)*100, 2)}%')
print('\nRuta:')
for i, city in enumerate(bestRoute):
print(f'{i+16}. {circuits1[city][1]}, {circuits1[city][2]}')
Complejidad: 24 posibles soluciones Total recorrido actual: 11014.56Km Total recorrido óptimo: 9907.65Km Mejora con respecto al actual: 10.05% Ruta: 16. Baku, Azerbaijan 17. Jeddah, Saudi Arabia 18. Sakhir, Bahrain 19. Lusail, Qatar 20. Abu Dhabi, United Arab Emirates 21. Marina Bay, Singapore
Aplicando las mejoras encontradas utilizando búsqueda exhaustiva se llega a la conclución de que el recorrido más óptimo para los 23 circuitos del calendario 2023 de la Formula 1 es:
Cabe aclarar que este orden puede darse de manera invesa, ya que las distancias recorridas son iguales y, Aunque no se tiene en cuenta en este trabajo, el orden inverso podría cumplir de mejor manera con otras resticciones en la realización de los Grandes Premios (Tales como cuestiones climáticas o religiosas)
circuits = [
('Autódromo José Carlos Pace', 'Sao Paulo', 'Brazil', -23.701111, -46.697222),
('Miami International Autodrome', 'Miami', 'United States', 25.958056, -80.238889),
('Autódromo Hermanos Rodriguez', 'Mexico City', 'Mexico', 19.406111, -99.0925),
('Circuit of the Americas', 'Austin', 'United States', 30.132778, -97.641111),
('Las Vegas Strip Circuit', 'Las Vegas', 'United States', 36.119684, -115.172599),
('Circuit Gilles Villeneuve', 'Montreal', 'Canada', 45.500556, -73.5225),
('Silverstone Circuit', 'Silverstone', 'United Kingdom', 52.078611, -1.016944),
('Circuit Zandvoort', 'Zandvoort', 'Netherlands', 52.388819, 4.540922),
('Circuit de Spa-Francorchamps', 'Spa-Francorchamps', 'Belgium', 50.437222, 5.971389),
('Circuit de Barcelona-Catalunya', 'Barcelona', 'Spain', 41.57, 2.261111),
('Circuit de Monaco', 'Montecarlo', 'Monaco', 43.734722, 7.420556),
('Autodromo Nazionale di Monza', 'Monza', 'Italy', 45.620556, 9.289444),
('Autodromo Internazionale Enzo e Dino Ferrari', 'Imola', 'Italy', 44.341111, 11.713333),
('Red Bull Ring', 'Spielberg', 'Austria', 47.219722, 14.764722),
('Hungaroring', 'Budapest', 'Hungary', 47.582222, 19.251111),
('Baku City Circuit', 'Baku', 'Azerbaijan', 40.3725, 49.853333),
('Jeddah Corniche Circuit', 'Jeddah', 'Saudi Arabia', 21.631944, 39.104444),
('Bahrain International Circuit', 'Sakhir', 'Bahrain', 26.0325, 50.510556),
('Lusail International Circuit', 'Lusail', 'Qatar', 25.49, 51.454167),
('Yas Marina Circuit', 'Abu Dhabi', 'United Arab Emirates', 24.467222, 54.603056),
('Marina Bay Street Circuit', 'Marina Bay', 'Singapore', 1.291531, 103.86385),
('Suzuka International Racing Course', 'Suzuka', 'Japan', 34.843056, 136.540556),
('Albert Park Circuit', 'Melbourne', 'Australia', -37.849722, 144.968333),
]
# Distancia recorrida actual en kilometros
optimalKilometers = 0
for i in range(1, len(circuits)):
optimalKilometers += haversineDistance(circuits[i-1], circuits[i])
# Resultados finales
print(f'Total recorrido actual: {round(currentTotalDistance, 2)} Km')
print(f'Total recorrido óptimo: {round(optimalKilometers, 2)} Km')
print(f'Mejora con respecto al actual: {round(((currentTotalDistance-optimalKilometers)/currentTotalDistance)*100, 2)}%')
Total recorrido actual: 132163.47 Km Total recorrido óptimo: 49364.9 Km Mejora con respecto al actual: 62.65%